Decode Ways

LeetCode 91 | Difficulty: Medium

Medium

Problem Description

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A'

"2" -> 'B'

...

"25" -> 'Y'

"26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

- `"AAJF"` with the grouping `(1, 1, 10, 6)`

- `"KJF"` with the grouping `(11, 10, 6)`

- The grouping `(1, 11, 06)` is invalid because `"06"` is not a valid code (only `"6"` is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"

Output: 2

Explanation:

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"

Output: 3

Explanation:

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"

Output: 0

Explanation:

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Constraints:

- `1 <= s.length <= 100`

- `s` contains only digits and may contain leading zero(s).

Topics: String, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 72 ms)

Metric	Value
Runtime	72 ms
Memory	22.8 MB
Date	2020-01-29

Solution

public class Solution {
    public int NumDecodings(string s) {
        if(string.IsNullOrEmpty(s)) return 0;
    int n = s.Length;
    int[] dp = new int[n+1];
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == '0') dp[i] = 0;
        else
        {
            dp[i] = dp[i + 1];
            if (i < n - 1 && (s[i] == '1' || (s[i] == '2' && ((int)s[i+1]-'0')<7))) dp[i] += dp[i + 2];
        }
    }
    return dp[0];
}
}

📜 2 more C# submission(s)

Submission (2018-03-22) — 112 ms, N/A

public class Solution {
    public int NumDecodings(string s) {
        if(string.IsNullOrEmpty(s)) return 0;
    int n = s.Length;
    int[] dp = new int[n+1];
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == '0') dp[i] = 0;
        else
        {
            dp[i] = dp[i + 1];
            if (i < n - 1 && (s[i] == '1' || (s[i] == '2' && ((int)s[i+1]-'0')<7))) dp[i] += dp[i + 2];
        }
    }
    return dp[0];
}
}

Submission (2018-03-22) — 156 ms, N/A

public class Solution {
    public int NumDecodings(string s) {
        if(string.IsNullOrEmpty(s)) return 0;
    int n = s.Length;
    int[] dp = new int[n+1];
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == '0') dp[i] = 0;
        else
        {
            dp[i] = dp[i + 1];
            if (i < n - 1 && (s[i] == '1' || (s[i] == '2' && (int)char.GetNumericValue(s[i + 1]) < 7))) dp[i] += dp[i + 2];
        }
    }
    return dp[0];
}
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.